package design.leetcode_146_lru;

import java.util.HashMap;

/**
 * @author panxingyu
 *
 * LRU缓存设计，利用双向链表 + 哈希表
 *
 * 双向链表的作用：
 *          快速实现缓冲区中数据的添加和删除（链表的特点：增删快、查找慢），下面使用的双向链表，头节点存最久未使用的数据，尾节点存最近使用的数据
 * 双向链表需要提供的方法：
 *          add2Tail(DoubleLinkedList node) : 添加节点，添加位置为表尾，代表新数据加入缓冲区
 *          removeHead()：删除头节点，头节点表示最近最久未使用的数据，当缓冲区满时，调用该方法。
 *          move2Tail(int key)：找到key对应的节点，移动到表尾。当用户调用某个节点的数据时，表示最近使用了该数据。
 * 哈希表的作用：
 *          解决双向链表查询慢的问题，这就决定了双向链表除了pre指针、next指针外，
 *                                  还需要存在额外的key：标识当前数据在缓冲区的位置；value：表示数据的值
 */
public class LRUCache2 {
    /**
     * 简单实现双向链表
     */
    private class DoubleLinkedList {
        private int key;
        private int value;
        private DoubleLinkedList pre;
        private DoubleLinkedList next;
        public DoubleLinkedList () {}
        public DoubleLinkedList(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    // 哈希表 + 双向链表作为缓存
    private HashMap<Integer, DoubleLinkedList> cache;
    // 缓存的容量
    private int capacity;
    private DoubleLinkedList head;
    private DoubleLinkedList tail;

    public LRUCache2(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<Integer, DoubleLinkedList>();
        head = new DoubleLinkedList();
        tail = new DoubleLinkedList();
        head.next = tail;
        tail.pre = head;
    }

    /**
     * 从缓存中获取指定关键字的值，不存在返回 -1
     * @param key   关键字
     * @return      关键字的值
     */
    public int get(int key) {
        if (cache.containsKey(key)) {   // 关键字存在于缓存中，返回关键字的值
            move2Tail(key);
            DoubleLinkedList node = cache.get(key);
            return node.value;
        }
        // 不存在则返回 -1
        return -1;
    }

    /**
     * 向缓存中写入一组「关键字 - 值」
     * @param key   关键字
     * @param value 值
     */
    public void put(int key, int value) {
        // 关键字已经存在于缓存中，更新关键字的值
        if (cache.containsKey(key)) {
            cache.get(key).value = value;
            move2Tail(key);
            return;
        }
        // 缓存容量已满，向缓存中写入数据前应删除最近最久未使用的数据值
        if (cache.size() == capacity) {
            DoubleLinkedList node = removeHead();
            cache.remove(node.key);
        }
        // 生成数据，添加到缓存中
        DoubleLinkedList node = new DoubleLinkedList(key, value);
        add2Tail(node);
        cache.put(key, node);
    }

    /**
     * 添加节点到双向链表的表尾
     * @param node  包含数据值的节点
     */
    private void add2Tail(DoubleLinkedList node) {
        node.next = tail;
        node.pre = tail.pre;
        tail.pre.next = node;
        tail.pre = node;
    }

    /**
     * 删除最近最久未使用的节点（规定头节点为最近最久未使用的节点）
     * @return  被删除的节点
     */
    private DoubleLinkedList removeHead() {
        DoubleLinkedList res = head.next;
        res.next.pre = res.pre;
        res.pre.next = res.next;
        return res;
    }

    /**
     * 将最近使用过的节点移动到表尾
     * @param key   与指定节点关联的 Key
     */
    private void move2Tail(int key) {
        DoubleLinkedList node = cache.get(key);
        node.next.pre = node.pre;
        node.pre.next = node.next;
        add2Tail(node);
    }

    public static void main(String[] args) {
        LRUCache2 cache = new LRUCache2(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));
        cache.put(3, 3);
        System.out.println(cache.get(2));
        cache.put(4, 4);
        System.out.println(cache.get(1));
        System.out.println(cache.get(3));
        System.out.println(cache.get(4));
    }
}
